package com.kavinz.alog.hashtable;

/**
 * Internally used by SeparateChainingHashTable.Use binary search.
 * 
 * @author Kevin Zhao
 * 
 */
public class SymbolTable {

	String[] keys = new String[100];
	Object[] values = new Object[100];

	/**
	 * 
	 * @param key
	 * @return
	 */
	public Object get(String key) {
		int rank = rank(key);
		// search hits
		if (keys[rank].compareTo(key) == 0) {
			return values[rank];
		}
		// search misses
		return null;
	}

	public void put(String key, Object value) {
		int rank = rank(key);
		// the specified key does not exist
		if (keys[rank] == null || keys[rank].compareTo(key) != 0) {
			// expanding the array
			for (int i = keys.length - 1; i > rank; i--) {
				keys[i] = keys[i - 1];
				values[i] = values[i - 1];
			}

		}
		// insertion
		if (keys[rank]!=null&&key.compareTo(keys[rank]) > 0) {
			keys[rank + 1] = key;
			values[rank + 1] = value;

		} else {
			keys[rank] = key;
			values[rank] = value;
		}

	}

	/**
	 * give the rank order of the key in the SymbolTable(Iterative)<BR>
	 * Note:either producing the exact index or the nearest left-hand index of
	 * the key
	 * 
	 * @param key
	 * @return -1
	 */
	private int rank(String key) {
		int lowerBoundry = 0;
		int upperBoundry = keys.length;

		while (lowerBoundry < upperBoundry) {
			int midLocation = (lowerBoundry + upperBoundry) / 2;
			String midKey = keys[midLocation];
			// key precedes midkey
			if (midKey == null || key.compareTo(midKey) < 0) {
				upperBoundry = midLocation - 1;
			}
			// key follows midkey
			else if (key.compareTo(midKey) > 0) {
				lowerBoundry = midLocation + 1;
			}
			// key equals midkey
			else {
				// return the exact index
				return midLocation;
			}
		}
		// return the nearest left-hand index
		return lowerBoundry;

	}

	public static void main(String[] args) {
		SymbolTable table = new SymbolTable();
		table.put("bafasd", "b");
		table.put("grhae", "g");
		table.put("jdsg", "j");
		table.put("eahq", "e");

		table.put("fsehseg", "f");
		table.put("faehseg", "f");
		table.put("cawgq", "c");

		System.out.println("bb".compareTo("ba"));
	}
}
